package TenBasicAlgorithm;

import java.util.Arrays;
//迪杰斯特拉(最短路径问题求出这点到个点的最短距离)
public class DijkstraDemo {
    public static void main(String[] args) {
        char[]vertex={'A','B','C','D','E','F','G'};
        final int N=65535;
        int[][]matrix=new int[vertex.length][vertex.length];
        matrix[0]=new int[]{N,5,7,N,N,N,2};
        matrix[1]=new int[]{5,N,N,9,N,N,3};
        matrix[2]=new int[]{7,N,N,N,8,N,N};
        matrix[3]=new int[]{N,9,N,N,N,4,N};
        matrix[4]=new int[]{N,N,8,N,N,5,4};
        matrix[5]=new int[]{N,N,N,4,5,N,6};
        matrix[6]=new int[]{2,3,N,N,4,6,N};
        Graph graph=new Graph(vertex,matrix);
        graph.showGraph();
        graph.dsj(6);
        graph.show();

    }
}

class Graph{
    public char[] vertex;
    public int[][]matrix;
    private VisitedVertex vv;
    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }
    public void showGraph(){
        for (int[] link:matrix) {
            System.out.println(Arrays.toString(link));
        }
    }
    public void dsj(int index){
         vv=new VisitedVertex(this.vertex.length,index);
         update(index);
        for (int i = 1; i < vertex.length; i++) {
            index=vv.updateArr();
            update(index);
        }


    }
    private void update(int index){
        int len=0;
        for (int i = 0; i < matrix[index].length; i++) {
            len=vv.getDis(index)+matrix[index][i];
            if(!vv.in(i)&&len<vv.getDis(i)){
                vv.updateDis(i,len);
                vv.updatePre(i,index);
            }
        }
    }
    public void show(){
        vv.show();
    }
}
class VisitedVertex{
    public int[] already_arr;
    public int[] pre_visited;
    public int[] dis;

    public VisitedVertex(int length,int index) {
        this.already_arr=new int[length];
        this.pre_visited=new int[length];
        this.dis=new int[length];
        Arrays.fill(dis,65535);
        this.already_arr[index]=1;
        this.dis[index]=0;
    }

    public boolean in(int index){//判断是否2被访问过
        return already_arr[index]==1;
    }
    public void updateDis(int index,int len){//更新距离
        dis[index]=len;
    }
    public void updatePre(int pre,int index){//更新前驱节点
        pre_visited[pre]=index;
    }
    public int getDis(int index){//返回距离
        return dis[index];
    }
    public void updateAlready_arr(int index){
        already_arr[index]=1;
    }
    public int updateArr(){
        int min=65535,index=0;
        for (int i = 0; i < already_arr.length; i++) {
            if(already_arr[i]==0&&dis[i]<min){
                min=dis[i];
                index=i;
            }
        }
        updateAlready_arr(index);
        return index;
    }
    public void show(){
        for (int i :already_arr) {
            System.out.print(i+" ");

        }System.out.println();
        for (int i :pre_visited) {
            System.out.print(i+" ");

        }System.out.println();
        for (int i :dis) {
            System.out.print(i+" ");

        }
    }

}